package greedy;
import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;

public class Ex1035 {
    class Solution {
        /* 
            输入：nums1 = [1,4,2], nums2 = [1,2,4]
            输出：2
            解释：可以画出两条不交叉的线，如上图所示。 
            但无法画出第三条不相交的直线，
            因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
        */
        public int maxUncrossedLines(int[] nums1, int[] nums2) {
            Map<Integer, List<Integer>> map = new HashMap<>();
            //可以保证，第一次出现该数的位置在最前方
            for (int i = 0; i < nums1.length; i++) {
                if (map.containsKey(nums1[i])) map.get(nums1[i]).add(i);
                else {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    map.put(nums1[i], list);
                }
            }

            Map<Integer, List<Integer>> map2 = new HashMap<>();
            //可以保证，第一次出现该数的位置在最前方
            for (int i = 0; i < nums2.length; i++) {
                if (map2.containsKey(nums2[i])) map2.get(nums2[i]).add(i);
                else {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    map2.put(nums2[i], list);
                }
            }

            Queue<int[]> queue = new PriorityQueue<>((i1, i2) -> i1[0] + i1[1] - (i2[0] + i2[1]));

            Map<Integer, Integer> used = new HashMap<>();
            for (int i : nums1) {
                if (map2.containsKey(i)) {
                    if (!used.containsKey(i)) used.put(i, -1);
                    int cur = used.get(i) + 1;
                    used.put(i, cur);
                    List<Integer> list1= map.get(i);
                    List<Integer> list2 = map2.get(i);
                    queue.offer(new int[]{list1.get(cur), list2.get(cur)});
                }
            }
            int last1 = -1, last2 = -1,  res = 0;
            int[] cur = null;
            while(!queue.isEmpty()) {
                cur = queue.poll();
                if (last1 + last2 != cur[1] + cur[0]) {
                    if (cur[1] > last1 && cur[1] > last2 && cur[0] > last1 && cur[1] > last2) {
                        res++;
                        last1 = cur[0];
                        last2 = cur[1];
                    }
                }
            }
            return res;
        }
    } //垃圾代码毁我青春

    //最长公共子序列问题
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        //f[i][j] 表示以nums[i]、nums2[j]为尾的前面这截子串所有的最大公共子序列
        int[][] f = new int[len1][len2];
        f[0][0] = nums1[0] == nums2[0] ? 1 : 0;
        if (f[0][0] == 1) {
            f[0][1] = 1;
            f[1][0] = 1;
        } else {
            f[0][1] = nums1[0] == nums2[1] ? 1 : 0;
            f[1][0] = nums1[1] == nums2[0] ? 1 : 0;
        }
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                f[i][j] = f[i - 1][j - 1]; //至少能有之前一位的最大长度
                if (nums1[i] == nums2[j]) {
                    f[i][j]++;
                }
                f[i][j] = Math.max(f[i][j], Math.max(f[i - 1][j], f[i][j - 1]));
            }
        }
        return f[len1 - 1][len2 - 1];
    } //问题：若以0表示没有字符，可以全部设为0为初始点，就不必上面的一堆if了

    public int maxUncrossedLines2(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        //f[i][j] 表示以nums[i]、nums2[j]为尾的前面这截子串所有的最大公共子序列
        int[][] f = new int[len1 + 1][len2 + 1];
        //f[0][0] f[0][1] f[1][0] 都表示至少有一个不存在，因此
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
               f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
               if (nums1[i - 1] == nums2[j - 1]) {
                   f[i][j] = Math.max(f[i - 1][j - 1] + 1, f[i][j]);
               }
            }
        }
        return f[len1][len2];
    }

    @Test
    public void test() {
        int[] nums1 = {5, 3, 2, 9, 9, 8, 7, 4, 9, 6, 6, 2, 9, 5, 5, 2, 3, 1, 5, 5};//{1, 4, 2}; [5, 3, 2, 9, 9, 8, 7, 4, 9, 6, 6, 2, 9, 5, 5, 2, 3, 1, 5, 5]
        // [7, 4, 6, 8, 8,10, 8, 6, 9, 10, 3, 1, 5, 4, 2, 1, 5, 8, 6, 6]
        int[] nums2 = {7, 4, 6, 8, 8,10, 8, 6, 9, 10, 3, 1, 5, 4, 2, 1, 5, 8, 6, 6};//{1, 2, 4};
        // int res = s.maxUncrossedLines(nums1, nums2);
        int res2 = maxUncrossedLines(nums1, nums2);
        System.out.println(res2);
    }


    @Test
    public void test2() {
        int[] nums1 = ArrayGenerator.getArray(10, 20);
        int[] nums2 = ArrayGenerator.getArray(10, 20);
        System.out.println(Arrays.toString(nums1));
        System.out.println(Arrays.toString(nums2));
    }
}
